package chapter_04;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
使用栈来逆序用户输入的字符串
 */


// 栈的效率
// 数据项入栈和出栈的时间复杂度都为常数O(1)。这也就是说，栈操作所耗的时间不依赖于
// 栈中数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

public class StackCharArray {
    private char[] charArray;
    private int maxSize;
    private int top;

    public StackCharArray(int s) {
        maxSize = s;
        charArray = new char[s];
        top = -1;
    }

    public void push(char j) {
        charArray[++top] = j;
    }

    public char pop() {
        return charArray[top--];
    }

    public boolean isEmpty() {
        return -1 == top;
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }
}


class Reverser {
    private String input;
    private String output;

    public Reverser(String in) {
        input = in;
    }

    public String doRev() {
        int stackSize = input.length();
        StackCharArray theStack = new StackCharArray(stackSize);

        // 入栈
        for (int j = 0; j < input.length(); j++) {
            char ch = input.charAt(j);
            theStack.push(ch);
        }
        output = "";
        // 出栈
        while ( !theStack.isEmpty() ) {
            char ch = theStack.pop();
            output += ch;
        }
        return output;
    }

    public static String getString() {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = null;
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    public static void main(String[] args) {
        String input, output;
        while ( true ) {
            System.out.println("Enter a string");
            System.out.flush();
            input = getString();
            if ( input.equals("quit") )
                break;

            Reverser theReverser = new Reverser(input);
            output = theReverser.doRev();
            System.out.println("Reversed: " + output);
        }
    }
}
